The goal of static timing analysis (STA) is to determine the latest and earliest possible switching times of various signals within a digital circuit. STA may generally be performed at the transistor level or at the gate level, using precharacterized library elements, or at higher levels of abstraction, for complex hierarchical chips and/or multi-chip packages.
STA algorithms operate by first levelizing the logic structure, and breaking any loops in order to create a directed acyclic graph (timing graph). Modern designs can often contain millions of placeable objects, with corresponding timing graphs having millions, if not tens of millions of nodes. For each node, a corresponding arrival time, transition rate (slew), and required arrival time are computed for both rising and falling transitions as well early and late mode analysis. An arrival time (AT) represents the latest or earliest time at which a signal can transition due to the entire upstream fan-in cone. The slew value is the transition rate associated with a corresponding AT, and a required arrival time (RAT) represents the latest or earliest time at which a signal must transition due to timing constraints in the entire downstream fan-out cone.
AT's are propagated forward in a levelized manner, starting from the design primary input asserted (i.e., user-specified) arrival times, and ending at either primary output ports or intermediate storage elements. For single fan-in cases,AT sink node=AT source node+delay from source to sink.
Whenever multiple signals merge, each fan-in contributes a potential arrival time computed asAT sink (potential)=AT source+delay,making it possible for the maximum (late mode) or minimum (early mode) of all potential arrival times to be retained at the sink node. Typically an exact delay value for an edge in a timing graph is not known, but instead only a range of possible delay values can be determined between some minimum delay and maximum delay. In this case, maximum delays are used to compute late mode arrival times and minimum delays are used to compute early mode arrival times.
RATs are computed in a backward levelized manner starting from either asserted required arrival times at the design primary output pins, or from tests (e.g., setup or hold constraints) at internal storage devices. For single fan-out cases,RAT source node=RAT sink node−delay.
When multiple fan-outs merge (or when a test is present), each fan-out (or test) contributes a prospective RAT, enabling the minimum (late mode) or maximum (early mode) required arrival time to be retained at the source node. When only a range of possible delay values can be determined, maximum delay are used to compute late mode required arrival times and minimum delays are used to compute early mode required arrival times.
The difference between the arrival time and required arrival time at a node (i.e., RAT−AT in late mode, and AT−RAT in early mode) is referred to as slack. A positive slack implies that the current arrival time at a given node meets all downstream timing constraints, and a negative slack implies that the arrival time fails at least one such downstream timing constraint. A timing point may include multiple such AT, RAT, and slew values, each denoted with a separate tag, in order to represent data associated with different clock domains (i.e., launched by different clock signals), or for the purpose of distinguishing information for a specific subset of an entire fan-in cone or fan-out cone.
Clock skew refers to the difference in arrival times between a given pair of clock inputs. Considering the case of a setup test, a slack can be computed as:Capture clock arrival time at test−data arrival time at test−setup time+cycle adjust which can also be expressed in terms of capture and launching clock arrival times as follows:Capture clock input arrival time+capture clock input to test delay−Launching clock input arrival time−Launching clock to test delay−setup time+cycle adjust
Grouping terms, it becomes:(Capture clock input arrival time−Launching clock input arrival time)+Capture clock input to test delay−Launching clock input to test delay−setup time+cycle adjust.
Therefore, it is evident that the slack at a given test depends on the skew between the launching and capturing clock inputs as expressed by the term (Capture clock input arrival time−Launching clock input arrival time).
Due to increasing design sizes, hierarchical static timing analysis techniques are becoming popular in order to divide analysis of a large design in to smaller and more manageable segments. In one style of hierarchical analysis, a design is partitioned into various modules which are analyzed independently (also referred hereinafter as “out of context” analysis), using asserted input arrival times and output required arrival times. A reduced abstract model is subsequently generated which may remove internal latch to latch logic, and full design timing is subsequently performed using reduced abstract models. In order to verify that internal logic continues to operate correctly in the full design level timing environment (i.e., all slacks in the original logic will be greater than zero, or a user-specified threshold), clock arrival times need to be examined to check for excessive skew which may lead to an internal timing failure.
Prior art approaches to the aforementioned problem are described, for instance, in U.S. Pat. No. 7,103,863 to Riepe et al., in which, a method for performing hierarchical static timing analysis is set forth whereby asserted arrival times at hierarchical inputs are translated in to absolute required arrival times for top-level timing. However, such approaches are pessimistic for clock validation in that they do not take in to account relative timing considerations. For example, in situations where multiple clock signals arrive at a hierarchical module, internal timing constraints may still be met in cases where all clock inputs are offset by the same amount relative to the out-of-context timing assertions, since in this scenario the relative skew between said clock inputs is constant (even though absolute arrival times have changed).
Another approach for hierarchical static timing analysis is described in “A Comprehensive Solution for True Hierarchical Timing and Crosstalk Delay Signoff” to Sivakumar, et. al., in which budgeted clock skew values are used to perform hierarchical timing sign off. In this approach, a particular clock skew is assumed during out-of-context validation, and then a corresponding clock skew test is performed during top-level timing to ensure consistency. This technique, however, does not take in to account any available positive slack observed during out-of-context timing analysis in order to relax skew constraints for top-level timing, and therefore can lead to pessimistic over-design.
Accordingly, there is a need for a system and a method for efficiently validating clock skews during hierarchical static timing analysis, which reduces pessimism as compared to prior art techniques while still ensuring that all internal timing constraints will continue to be satisfied.